Chameleon Hash Functions |
您所在的位置：网站首页 › 变色龙 原理 › Chameleon Hash Functions |
Chameleon Hash Functions
|
Chameleon Hash Functions（变色龙哈希）
文章目录 Chameleon Hash Functions（变色龙哈希）前言一、变色龙Has是什么？二、变色龙散列基于无爪陷门排列三、 基于离散对数的变色龙哈希四、数字签名五、Github源码 前言提示：这篇博客是我在阅读论文后根据自己的理解写的，可能有些翻译不准确，欢迎大家指正！ 提示：以下是本篇文章正文内容，下面案例可供参考 一、变色龙Has是什么？传统哈希函数的难以找到碰撞，变色龙哈希可以人为的设一个“弱点”或者“后门”：掌握了这个后门就可以轻松的找到哈希碰撞。 这种设计在一定程度上破坏了哈希函数的两个碰撞性的特点，同时，也破坏了基于哈希函数的区块链的不可篡改的特性，但是也扩大了区块链的应用场景，而且对于不知道门限的普通用户来说，想要找到碰撞依然是不可行的，也就是说，变色龙哈希的安全性也是可以保障的，对于持有“后门”的管理人员，如果其随意篡改区块，也是可以通过验证两个区块的哈希是否相等来验证。 用户R的公钥表示为 H K R HK_R HKR 私钥（陷门） C H R CH_R CHR, 公钥 H K R HK_R HKR定义了一个变色龙散列函数， c h a m − h a s h R ( ) cham-hash_R() cham−hashR() 在输入消息m和随机字符串r时，该函数生成哈希值 c h a m − h a s h R ( m , r ) cham-hash_R(m,r) cham−hashR(m,r)，满足以下属性： 抗碰撞: 在输入公钥HKR时，没有 m 1 = m 2 m_1 = m_2 m1=m2算法可以对 c h a m − h a s h R ( m 1 , r 1 ) = c h a m − h a s h R ( m 2 , r 2 ) cham-hash_R(m_1,r_1) = cham-hash_R(m_2,r_2) cham−hashR(m1,r1)=cham−hashR(m2,r2)，除非概率可以忽略不计。陷门碰撞： 在输入秘钥 C H R CH_R CHR时，任意对 m 1 ； r 1 m_1；r_1 m1；r1都可以找到值 m 2 , r 2 m_2,r_2 m2,r2，使得 c h a m − h a s h R ( m 1 , r 1 ) = c h a m − h a s h R ( m 2 , r 2 ) cham-hash_R(m_1,r_1) = cham-hash_R(m_2,r_2) cham−hashR(m1,r1)=cham−hashR(m2,r2)统一: 特别是，从随机选择的r中看到 c h a m − h a s h R ( m , r ) cham-hash_R(m,r) cham−hashR(m,r))，对m一无所知，以要求上述分布对于所有消息不一定相同，但在计算上无法区分变色龙散列函数旨在作用于任意长的消息，并生成固定长度的输出。 示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。 二、变色龙散列基于无爪陷门排列我们提出了一种基于无爪陷阱门排列的变色龙散列的一般结构，以及一种基于保理硬度的具体实现。 这个构造方法是最新的由Goldwasser、Micali和Rivest[GMR88]介绍，用于构建常规数字签名，并由Damgard[Dam87]用于构建抗碰撞哈希函数。 我们使用t的陷门信息，提供变色龙哈希的发现陷门碰撞特性。 在一个公共域上，如果它在计算上不可能从域中得到值x和y，使得 f 0 ( X ) = f 1 ( Y ) f_0(X)=f_1(Y) f0(X)=f1(Y)，则称为（claw-free)。 一对排列 ( f 0 ( X ) ； f 1 ( X ) ) (f_0(X)；f_1(X)) (f0(X)；f1(X)) 我们将长度k的消息m的二进制表示为m=m[1]…m[k]，其中m[1]是消息第一位，m[k]是最后一位。 私钥: ( f 0 − 1 , f 1 − 2 ) (f_0^{-1},f_1^{-2}) (f0−1,f1−2) 公钥: ( f 0 , f 1 ) (f_0,f_1) (f0,f1) 消息:m=m[1]…m[k] Hash:值 c h a m − h a s h ( f 0 , f 1 ) ( m , r ) = f m [ k ] ( . . . ( f m [ 2 ] ( f m [ 1 ] ( r 1 ) ) ) ) cham-hash_{(f_0, f_1)}(m,r)=f_{m[k]}(...(f_{m[2]}(f_{m[1]}(r_1)))) cham−hash(f0,f1)(m,r)=fm[k](...(fm[2](fm[1](r1)))) 对于消息 m 2 m_2 m2,求 r 2 : r_2: r2: f m 2 [ k ] − 1 ( . . . ( f m 2 [ 2 ] − 1 ( f m 2 [ 1 ] − 1 ( c h a m − h a s h ( m 1 , r 1 ) ) ) ) ) f_{m_2[k]}^{-1}(...(f_{m_2[2]}^{-1}(f_{m_2[1]}^{-1}(cham-hash(m_1,r_1))))) fm2[k]−1(...(fm2[2]−1(fm2[1]−1(cham−hash(m1,r1))))) 例子： 选择两个素数p=3, q = 7 , n = pq=21 f 0 ( x ) = x 2 m o d n f_0(x) = x ^2modn f0(x)=x2modn f 1 ( x ) = 4 x 2 m o d n f_1(x) = 4x ^2modn f1(x)=4x2modn D = { x ∣ ( x p ) = ( x q ) = 1 } D=\{x | (\frac{x}{p}) = (\frac{x}{q}) = 1\} D={x∣(px)=(qx)=1}保证x是模p，q的二次剩余 消息x1=101,r1=8 step1: 4 ∗ 8 ∗ 8 m o d 21 = 4 4 * 8 * 8 mod 21 = 4 4∗8∗8mod21=4 step2: 4 ∗ 4 m o d 21 = 16 4 * 4 mod 21 = 16 4∗4mod21=16 step3: 4 ∗ 16 ∗ 16 m o d 21 = 16 4 * 16 * 16 mod 21 = 16 4∗16∗16mod21=16 c h a m − h a s h ( f 0 , f 1 ) ( m , r ) = c h a m − h a s h ( f 0 , f 1 ) ( 101 , 8 ) = 16 cham-hash_{(f_0, f_1)}(m,r)=cham-hash_{(f_0, f_1)}(101,8)=16 cham−hash(f0,f1)(m,r)=cham−hash(f0,f1)(101,8)=16 消息x2=110,r2=？ step1: f 0 − 1 ( 16 ) = 4 f_0^{-1}(16) = 4 f0−1(16)=4 step2: f 1 − 1 ( 4 ) = 1 f_1^{-1}(4) = 1 f1−1(4)=1 step3: f 1 − 1 ( 1 ) = 4 f_1^{-1}(1) = 4 f1−1(1)=4 r 2 = 4 r_2=4 r2=4 验证： 消息x2=110,r2=4 step1: 4 ∗ 4 ∗ 4 m o d 21 = 1 4 * 4 * 4 mod 21 = 1 4∗4∗4mod21=1 step2: 4 m o d 21 = 4 4 mod 21 = 4 4mod21=4 step3: 4 ∗ 4 m o d 21 = 16 4 * 4 mod 21 = 16 4∗4mod21=16 c h a m − h a s h ( f 0 , f 1 ) ( m , r ) = c h a m − h a s h ( f 0 , f 1 ) ( 110 , 4 ) = 16 cham-hash_{(f_0, f_1)}(m,r)=cham-hash_{(f_0, f_1)}(110,4)=16 cham−hash(f0,f1)(m,r)=cham−hash(f0,f1)(110,4)=16 三、 基于离散对数的变色龙哈希Hugo Krawczky 和 Tal Rabin 在2000年提出了变色龙哈希方案，具体方案描述如下： Setup(λ):输入安全性参数λ ，构造满足安全性参数λ 的大素数p,q,其中p，q满足p=kq+1,选取乘法循环群 Z p ∗ Z^{*}_p Zp∗中阶为q的元素g， 输出公共参数pp=（p,q,g）； KeyGen(pp):输入公共参数pp，在乘法循环群 Z p ∗ Z^{*}_p Zp∗中随机选择指数x，计算 h = g x h=g^x h=gx，最后得到私钥CK=x，公钥HK=h； Hash(HK,m,r):输入公钥HK，消息m，随机数r，其中m，r均为 Z p ∗ Z^{*}_p Zp∗中元素，输出变色龙哈希值 C H = g m h r m o d p CH=g^mh^r mod p CH=gmhrmodp; Forge（CK，m，r，m’）： 输入私钥，CH=x，消息m，随机数r，消息m’,其中m,r, m’,均为 Z p ∗ Z^{*}_p Zp∗中的元素， 根据 C H = g m h r m o d p = g m ‘ h r ‘ m o d p CH=g^mh^r mod p=g^{m^`}h^{r^`}mod p CH=gmhrmodp=gm‘hr‘modp,可得 m + x r = ( m ‘ + x r ‘ ) m o d p m+xr=(m^`+xr^`) mod p m+xr=(m‘+xr‘)modp,继而可计算出 r ’ = ( m − m ’ + x r ) x − 1 m o d p r’=(m-m’+xr)x^{-1} mod p r’=(m−m’+xr)x−1modp。 **参数选择：**p，q满足p=kq+1，乘法循环群 Z p ∗ Z^{*}_p Zp∗中阶为q的元素g 私钥： C H = x CH=x CH=x 公钥: H K = h = g x HK=h=g^x HK=h=gx **消息：**m **随机数：**r 变色龙哈希值 C H = g m h r m o d p CH=g^mh^r mod p CH=gmhrmodp; 消息： m 2 m_2 m2 目标： C H = g m h r m o d p = g m ‘ h r ‘ m o d p CH=g^mh^r mod p=g^{m^`}h^{r^`}mod p CH=gmhrmodp=gm‘hr‘modp, 可得 m + x r = ( m ‘ + x r ‘ ) m o d p m+xr=(m^`+xr^`) mod p m+xr=(m‘+xr‘)modp, 继而可计算出 r ’ = ( m − m ’ + x r ) x − 1 m o d p r’=(m-m’+xr)x^{-1} mod p r’=(m−m’+xr)x−1modp。 私钥：x=2, g=3,q=3,p=kq+1=13 公钥： g x = 3 2 m o d 13 = 9 g^x=3^2mod13=9 gx=32mod13=9 m = 2 , r = 1 m=2,r=1 m=2,r=1 c h a m − h a s h ( 4 , 2 ) = g m h r = 3 2 9 1 m o d 13 = 81 m o d 13 = 3 cham-hash(4,2)=g^mh^r = 3^2 9^{1}mod13=81mod13=3 cham−hash(4,2)=gmhr=3291mod13=81mod13=3 m ‘ = 0 m^`=0 m‘=0 r ’ = ( m − m ’ + x r ) x − 1 m o d p = 4 ∗ 2 − 1 m o d 13 = 2 r’=(m-m’+xr)x^{-1} mod p =4*2^{-1}mod 13=2 r’=(m−m’+xr)x−1modp=4∗2−1mod13=2 验证： c h a m − h a s h ( 0 , 2 ) = g m h r = 3 0 9 2 m o d 13 = 81 m o d 13 = 3 cham-hash(0,2)=g^mh^r = 3^0 9^{2}mod13=81mod13=3 cham−hash(0,2)=gmhr=3092mod13=81mod13=3 c h a m − h a s h ( 2 , 1 ) = c h a m − h a s h ( 0 , 2 ) cham-hash(2,1)=cham-hash(0,2) cham−hash(2,1)=cham−hash(0,2) 四、数字签名变色龙哈希函数非常有意思。传统加密哈希函数是很难找到碰撞的。变色龙哈希函数可以人为设下一个“弱点”：掌握了它就能轻松找到碰撞。就好比一扇上锁的门，有对应的钥匙就能通过。 但是有谁吃饱了撑的故意设计弱化的哈希函数呢？这就要涉及到一个伴随因特网自始至终的信任问题，电子签名。传统电子签名过程是先用哈希函数把文件过一遍生成摘要，再用非对称加密里的私钥对摘要进行签名，这样其他人就能用对应的公钥验证文件的哈希有没有变化。如果哈希没变化，那么文件就没被更改。 但是这种设计有它的不足。假设小明和小红达成协议，小明将家族产业10%股份转让给小红。签了合同小名很担心啊，如果小红把这件事告诉别人怎么办？这时候就可以用变色龙函数进行签名。小红生成一个只有她才能找到碰撞的函数交给小明，小明再用这个函数来签电子文档。这下小红把签名后的文件丢给大家也没人相信她了。为什么呢？她掌握着哈希函数的弱点，可以随便生成哈希碰撞啊。她把10%股份改成99%都能保证哈希不会变，进而创造出新文件本来就是小明签的这种假象。因此出自小红之手的文件可信度为零。这个特性叫non-transferability，即两者之间达成的信任不能转到第三方。 “你知道的太多了” 此时此刻成了真正的包袱。 问题来了，小明抵赖怎么破？如果小明死死咬定转让10%股份是小红伪造，事实上只有1%呢？事实上小明也不能信口开河，他得提供对应的证据。证据就是哈希碰撞。假设双方达成的最初合同是A，而小红将其篡改成了相同哈希的A’，那么小明看到A’这份伪证之后一定能拿出最早那个A来并表明A和A’形成哈希碰撞，否则A’就是真货了。因为正常情况下小明无论如何也找不到碰撞，他就不能抵赖。这个特性叫non-repudiation。 首先， 变色龙签名具有不可传递性: 其合法性只能由签名者所指定的接收者来验证, 而其他任何人都不能确定该签名是由签名者所签的, 还是由指定接收者伪造的. 其次，变色龙签名具有不可伪造性: 对于一个伪造的变色龙签名,合法的签名者能够提供证据表明该伪造签名的不合法性. 再者, 变色龙签名具有不可否认性: 对于合法的变色龙签名, 其签名者并不能提供此类证明以开脱责任. 既然变色龙签名能够同时提供不可否认性, 不可伪造性和不可传递性, 所以变色龙签名是一种比较理想的指定验证者签名. 构造变色龙签名的主要工具是变色龙哈希函数. 更具体地讲, 变色龙签名的构造遵循了著名的先哈希再签名的范例(hash-and-sign paradigm), 但是稍有不同. 也就是说, 用来计算消息摘要的是变色龙哈希函数, 而不是普通的哈希函数; 用来计算签名的则是一个安全的数字签名算法. 变色龙哈希函数是一种带陷门的抗碰撞哈希函数: 对于知道其陷门的用户来说, 寻找该哈希函数的碰撞是非常容易的; 而对于不知道其陷门的用户来说, 这种哈希函数与一个标准的哈希函数一样是抗碰撞的. 既然变色龙签名是作用到消息摘要的一个函数, 而此消息摘要又是一个变色龙哈希值, 且陷门属于指定接收者, 所以指定验证者可以把一个变色龙签名变成是其他消息的签名. 
五、Github源码
单一帧添加我发哥的水印
运行代码： calculating... q= 7076412147999344709848440438228952875717 p= 34377210214980816600443723648916253070233187 g= 4003 SK= 5436429092544353106088843605389875260377 PK= 7725592492408161713638690353041010273814722 msg1= i sent first message rand1= 1674181499801353348207492416622746708885 CH= 22072510447255878935850254532181551499522989 msg2= second message rand2= 610322978229803970975139617333478732290 newCH= 22072510447255878935850254532181551499522989说明：使用下面的源码，需要安装一个素数的库，这里需要再安装一个VC的环境，否则会报错 Github源码地址：https://github.com/Zipzapztc/ChameleonHash本文参考文献： Krawczyk H M , Rabin T D . Chameleon hashing and signatures: US 2000.我给大家整理了一下，做了一个集成，如下： # n个用户，n个PK,SK,r，CH=g^m*h1^r1*h2^r2……hn^rn mod p # Setup(),KeyGen(),ChameleonHash(),Forge()四个函数 import random from pyunit_prime import get_large_prime_length # 随机生成指定长度大素数 from pyunit_prime import is_prime # 判断素数 from pyunit_prime import prime_range # 输出指定区间素数 import math random.seed(45687) # p=0 # q=0 p = 52650424227621396410011 q = 83572101948605391127 g = 358 length = 20 def primeFactorization(length): # 分解质因数 # global p,q p, q = 0, 0 q = get_large_prime_length(length) while True: d = random.randint(2, 10000) if d % 2 == 0: p = q * d + 1 if is_prime(p) == True: break else: continue else: continue primeList = prime_range(2, int(math.sqrt(d))) result = [[0, 0] for i in range(len(primeList))] for i in range(len(primeList)): result[i][0] = primeList[i] while d % primeList[i] == 0: result[i][1] += 1 d = d // primeList[i] if d != 1: result.append([d, 1]) result.append([q, 1]) return result, p, q def quickPower(a, b, c): # 快速幂，a^b mod c result = 1 while b > 0: if b % 2 == 1: result = result * a % c a = a * a % c b >>= 1 return result def getGenerator(result, p, q): # get g generator = random.randint(1, 1000) while True: if quickPower(generator, q, p) != 1: generator += 1 else: for i in range(len(result)): if quickPower(generator, int((p - 1) / result[i][0]), p) == 1: break if i != len(result) - 1: generator += 1 else: break return generator def Setup(length): factorization, p, q = primeFactorization(length) g = getGenerator(factorization, p, q) return p, q, g def getSecretKey(n, q): # get SKlist,x1,x2……xn SKlist = [] for _ in range(n): SKlist.append(random.randint(1, q)) return SKlist def getPublicKey(g,x): #get PK,h h=quickPower(g,x,p) return h def KeyGen(p, q, g, n): SKlist = getSecretKey(n, q) PKlist = getPublicKey(g, SKlist, n, p) return SKlist, PKlist def getr(n, q): # rlist,r1,r2……rn rlist = [] for _ in range(n): rlist.append(random.randint(1, q)) return rlist def treatMSG(msg): # 处理消息msg为整数 newmsg = '' for i in msg: newmsg += str(ord(i)) return int(newmsg) def ChameleonHash(PK,g,m,r): #变色龙哈希 CH=quickPower(g,m,p)*quickPower(PK,r,p)%p return CH def exgcd(a, b): # 扩展欧几里得 if b == 0: return 1, 0, a else: x, y, gcd = exgcd(b, a % b) x, y = y, (x - (a // b) * y) return x, y, gcd def Forge(SK,m1,r1,m2): #求r' x,y,gcd=exgcd(SK,q) result=x*(m1-m2+SK*r1)%q return result def CHhashAPI(msg1, msg2, SK, rand1): PK = getPublicKey(g, SK) newmsg1 = treatMSG(msg1) newmsg2 = treatMSG(msg2) rand2 = Forge(SK, newmsg1, rand1, newmsg2) newCH = ChameleonHash(PK, g, newmsg2, rand2) return {"CH": newCH, "rand": rand2} def CH(msg, SK): PK = getPublicKey(g, SK) newmsg1 = treatMSG(msg) rand1 = random.randint(1, q) # r CH = ChameleonHash(PK, g, newmsg1, rand1) return {"CH": str(CH), "rand": str(rand1), "PK":str(PK)} if __name__ == "__main__": SK = 48410017351108122866 msg1 = 'woshidiyunlong' # 消息m1 msg2 = 'second message' # 消息m2 result = CH(msg1 ,SK) print(result) # int(result['rand']) 就是r1 print(CHhashAPI(msg1, msg2, SK, int(result['rand'])))
有帮助的给小弟点个赞，给你比个💗💗哟
|
【本文地址】
今日新闻 |
推荐新闻 |